This invention relates generally to network communications and, more particularly, to routing a communication packet through a network switch device.
Ethernet networks typically do not require explicit programming of routing tables in a network switch device. A network switch device automatically learns routing by observing Media Access Control (MAC) addresses of communication packets (i.e., Ethernet frames) entering to the network switch device. MAC address is a quasi-unique identifier or physical address assigned to network adapters or network interface cards, e.g., by their manufactures. If a communication packet from a MAC address x enters at switch port y, the switch device makes an entry in its routing table to route the packet destined to the address x through the port y. When a communication packet arrives for which no entry exists in the routing table, the switch device broadcasts the packet to all ports except the port at which the packet arrived. Thus, each network switch device discovers a route to each end node (e.g., a computing device that an end user uses), assuming that all end nodes generate some packets that reach the switch device.
However, this broadcasting mechanism does not work with a network that has a loop because the broadcast mechanism can cause “broadcast storms” of communication packets being replicated in the loop ad infinitum. Thus, Ethernet networks traditionally have a tree structure to prevent the loop. The broadcast storm refers to a state in which a communication packet that has been broadcast across a network results in even more responses, and each response results in still more responses. A broadcast storm can block all other network traffic.
To avoid loops in a network, traditional solutions employ a spanning tree protocol that must execute on the network to determine which switch ports may be used and which ports should be disabled, transforming a physical topology of the network (which may include loops) into a logical topology without loops. However, employing the spanning tree protocol can negate multi-path routing capabilities of the network. Multi-path routing refers to a routing technique where forwarding a communication packet to a single destination address can occur over multiple paths, which can yield a variety of benefits such as a fault tolerance, an increased bandwidth, or an improved security. The spanning tree protocol (STP) refers to a network protocol that guarantees a loop-free topology in a Local Area Network (LAN). The STP allows a network to include spare (redundant) links to provide automatic backup paths if an active link fails, without creating a loop or a need for manual enabling/disabling of these backup links. The STP is defined in IEEE standard 802.1D.
Any network with bidirectional links and multi-path routing capabilities from a source node to a destination node automatically has a loop in it. Hence, broadcasting a communication packet to discover a route can cause broadcast storms in the network having multi-path routing capabilities. Convergence Enhanced Ethernet networks often have multi-path routing capabilities. The Convergence Enhanced Ethernet refers to an enhanced Ethernet that enables convergence of various applications in data centers onto a single interconnect technology. Ko et al., “A Case for Convergence Enhanced Ethernet: Requirements and Applications”, IEEE International Conference on Communications, 2008 (ICC 2008), 19-23 May 2008 Page(s):5702-5707, wholly incorporated by reference as set forth herein, describes the Convergence Enhanced Ethernet in detail.
Some traditional solutions employ a multiple spanning tree (MST) protocol within a network. IEEE standard 802.1Q, which is supported by most Ethernet hardware, specifies an operation of virtual local area network (VLAN) bridges, which support VLAN operation within an IEEE 802 bridged LAN. The MST protocol (IEEE standard 802.1s) adds facility for VLAN bridges to use multiple spanning trees, providing communication packet(s) belonging to different VLANs to flow over potentially different paths within the virtual bridged LAN. According to the MST protocol, by defining multiple VLANs, each of which having its own spanning tree, it is possible to provide multiple paths between any pair of source and destination nodes. However, each spanning tree provides exactly one path between a source node and a destination node. Thus, each alternative path requires an additional VLAN.
However, the traditional solutions employing the MST protocol may have limited scalability and reduction of VLAN address space. Currently, the VLAN identifier comprises 12 bits, allowing for up to 4,096 VLANs. This implies that, in principle, each switch device can maintain up to 4,096 different routing tables, one per VLAN. On the other hand, a total number of alternative paths is also limited to 4,096. However, many topologies have an arbitrarily large number (e.g., >1012) of possible paths between two end nodes, although the alternative paths are usually constrained to loop-free paths. For example, in a 2D n×n mesh network, there are (2×(n−1))!/((n−1)!×(n−1)!) shortest paths between nodes at opposite corners of the mesh. Specifically, when there are 11 nodes (i.e., n=11) in the 2D n×n mesh network, there are 184,756 paths. When there are 21 nodes in the network, there are 137,846,528,820 paths.
Fat tree network is a universal network configured for efficient communication. Links in a fat tree network become fatter as one moves up the tree toward a root of the tree. By choosing fatness of the links, the network can be tailored to efficiently use bandwidth made available or overcome bottlenecks in the network. The fat tree network provides the number of alternative shortest paths according to the number of switches in a top level of the tree. For example, in a 3-level fat tree built out of 32-port switches (i.e., a fat tree network having 8,192 nodes (32×16×16=8,192) and 1,280 switches (512+512+256=1,280 switches)), there are up to 256 paths per pair of end nodes. In this example, one spanning tree may be rooted on each top-level switch.
Thus, it is highly desirable to provide a network switching method and system that allow self-learning (e.g., discovering routes by broadcasting a packet) of a routing table in a network with multi-path capabilities without causing broadcast storm and without requiring implementation of the STP, MST protocol and without manual route configuration.